'''
https://leetcode.cn/problems/word-ladder/
'''
from typing import List



class Solution:
    def ladderLength(self, beginWord: str, endWord: str, wordList: List[str]) -> int:
        n = len(beginWord)
        dic = set(wordList)
        if endWord not in dic: return 0
        small_nodes, big_nodes = {beginWord}, {endWord}
        visited = set()
        step = 2
        while small_nodes:
            next_nodes = set()
            for word in small_nodes:
                for i in range(n):
                    old_char = word[i]
                    for char in 'abcdefghijklmnopqrstuvwxyz':
                        if char != old_char:
                            new_word = word[:i] + char + word[i+1:]
                            if new_word in big_nodes:
                                return step
                            if (new_word not in visited) and (new_word in dic):
                                next_nodes.add(new_word)
                                visited.add(new_word)
            step += 1
            small_nodes = next_nodes    if len(next_nodes) < len(big_nodes)     else big_nodes
            big_nodes   = big_nodes     if len(next_nodes) < len(big_nodes)     else next_nodes
        return 0

beginWord = "hit"
endWord = "cog"
wordList = ["hot","dot","dog","lot","log"]
s = Solution()
print(s.ladderLength(beginWord, endWord, wordList))
